In development and optimization of a program, it is important to know behavior of the program in detail. As analysis techniques used for knowing behavior of a program, techniques such as a CPU emulator, a software profiler, and a hardware profiler are available. In the CPU-emulator technique, a program is executed on a software CPU emulator. The CPU-emulator technique can provide every piece of information including an internal state of a processor but has low execution speed and cannot reproduce a real use environment of embedded devices. In the software-profile technique, instructions for analysis are inserted when a program is compiled. The software-profile technique measures the execution order, the number of times of execution, and the execution time in units of functions but the instructions for analysis greatly affect behavior of the program. The hardware-profiler technique is implemented in a CPU and hardware for analysis is added to a bus or a dedicated interface of the CPU. The analysis performance of the hardware-profiler technique depends on implementation and the hardware-profiler technique works only when the hardware for analysis is implemented.
PTL 1 discloses a technique in which both BHT-based branch prediction and non-BHT-based branch prediction (static branch prediction) are used. The BHT is not updated when an outcome can be statically predicted, whereby the technique prevents unnecessary rewriting of a value of the BHT from decreasing the accuracy of branch instruction prediction that requires the BHT.
PTL 2 discloses a branch prediction apparatus including a branch prediction table, a prediction output unit, and a counter control unit. The branch prediction table holds, for each branch instruction, a one-bit history bit and a two-bit counter. When a value of the counter is equal to zero or two, the prediction output unit outputs a value of the history bit. When the value of the counter is equal to one or three, the prediction output unit inverts the value of the history bit before outputting it. The counter control unit compares a branch result with the value of the history bit. If the branch result matches the value of the history bit, the counter control unit sets the value of the counter to zero. If the branch result does not match the value of the history bit and the value of the counter is not equal to three, the counter control unit increases the value of the counter by one. With the configuration, the branch prediction apparatus correctly predicts, using a few hardware components, a pattern in which “branch taken” and “branch not taken” alternately continue.